package mid.class4;

import cn.hutool.core.comparator.VersionComparator;
import com.sun.xml.internal.ws.util.VersionUtil;
import common.UnionFind;

import java.math.BigDecimal;

/**
 * https://leetcode.cn/problems/couples-holding-hands/
 * 情侣牵手问题
 * 情侣：{0,5,2,4,6,8,7,3,9,1}
 *
 * <p>
 * 解题思路：
 * *1.原数组：[0,5,2,4,6,8,7,3,9,1]
 * *2.成对组：
 * *		组0:[0,1]
 * *		组1:[2,3]
 * *		组2:[4,5]
 * *		组3:[6,7]
 * *		组4:[8,9]
 * *3.找到对应组：
 * *数： [0,5 , 2,4 , 6,8 , 7,3 , 9,1]
 * *组: [{0 2},{1 2},{3 4},{3 1},{4 0}]
 * *4.合并：
 * *    父: [0,1,2,3,4]   10个人分成5组
 * *	第1轮：0,5 合并成{0,2}    father:[2,1,2,3,4] index_0的代表值变为2
 * *	第2轮：2,4 合并成{0,1,2}  father:[2,2,2,3,4]
 * *	第3轮：6,8 合并成{3,4}    father:[2,2,2,4,4]
 * *	第4轮：3,1 合并成{0,1,2,3,4}    father:[2,2,2,4,2]
 * *	第5轮：4,0 合并成{0,1,2,3,4}    father:[2,2,2,4,2]
 * <p>
 * *	n-sets = 4;
 * *5.验证需要调整
 * *  4,5,2,0,6,8,7,3,9,1 -1
 * *  4,5,1,0,6,8,7,3,9,2 -2
 * *  4,5,1,0,6,8,7,9,3,2 -3
 * *  4,5,1,0,6,7,8,9,3,2 -4
 * <p>
 * * {0,1,2,3,4}   5-1 =4
 */
public class Code03_minSwapsCouples {

    public static void main(String[] args) {
        int[] arr = {0, 5, 2, 4, 6, 8, 7, 3, 9, 1};
        int i = minSwapsCouples(arr);
        System.out.println("i = " + i);
    }

    public static int minSwapsCouples(int[] row) {
        int n = row.length;
        UnionFind unionFind = new UnionFind(n / 2);
        for (int i = 0; i < n; i += 2) {
            unionFind.union(row[i] / 2, row[i + 1] / 2);
        }
        return n / 2 - unionFind.sets;
    }


}
